package linkedList;

import sun.awt.windows.ThemeReader;

import java.util.Stack;

/**
 * 带头节点的单链表
 */
public class SingleLinkedListDemo {
    public static void main(String[] args) {
        //进行测试
        //先创建节点
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode hero3 = new HeroNode(6, "吴用", "智多星");
        HeroNode hero4 = new HeroNode(10, "林冲", "豹子头");

        HeroNode hero5 = new HeroNode(5, "宋江", "及时雨");
        HeroNode hero6 = new HeroNode(7, "卢俊义", "玉麒麟");
        HeroNode hero7 = new HeroNode(8, "吴用", "智多星");
        HeroNode hero8 = new HeroNode(9, "林冲", "豹子头");

        //创建要给链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        SingleLinkedList singleLinkedList1 = new SingleLinkedList();
//
//
//        //加入
        singleLinkedList.add(hero1);
        singleLinkedList.add(hero2);
        singleLinkedList.add(hero3);
        singleLinkedList.add(hero4);

        singleLinkedList1.add(hero5);
        singleLinkedList1.add(hero6);
        singleLinkedList1.add(hero7);
        singleLinkedList1.add(hero8);

        SingleLinkedList combineSortedList = new SingleLinkedList();
        HeroNode combineSortedHead = SingleLinkedList.combineSortedList(singleLinkedList.getHead(), singleLinkedList1.getHead());
        combineSortedList.setHead(combineSortedHead);
        combineSortedList.list();


        // 测试一下单链表的反转功能
//        System.out.println("原来链表的情况~~");
//        combineSortedList.list();

//        System.out.println(singleLinkedList.size(singleLinkedList.getHead()));

//		System.out.println("反转单链表~~");
//		reversetList(singleLinkedList.getHead());
//		singleLinkedList.list();

//        System.out.println("测试逆序打印单链表, 没有改变链表的结构~~");
//        reversePrint(singleLinkedList.getHead());

		//加入按照编号的顺序
//		singleLinkedList.addByOrder(hero1);
//		singleLinkedList.addByOrder(hero4);
//		singleLinkedList.addByOrder(hero2);
//		singleLinkedList.addByOrder(hero3);
//
//		//显示一把
//		singleLinkedList.list();

		//测试修改节点的代码
//		HeroNode newHeroNode = new HeroNode(2, "小卢", "玉麒麟~~");
//		singleLinkedList.update(newHeroNode);

//		System.out.println("修改后的链表情况~~");
//		singleLinkedList.list();

		//删除一个节点
//		singleLinkedList.del(1);
//		singleLinkedList.del(4);
//		System.out.println("删除后的链表情况~~");
//		singleLinkedList.list();

		//测试一下 求单链表中有效节点的个数
//		System.out.println("有效的节点个数=" + getLength(singleLinkedList.getHead()));//2

		//测试一下看看是否得到了倒数第K个节点
//		HeroNode res = findLastIndexNode(singleLinkedList.getHead(), 3);
//		System.out.println("res=" + res);
}
}

/**
 * 定义链表
 */
class SingleLinkedList {
    //初始化头节点 不动他
    private HeroNode head = new HeroNode(0, "", "");

    public HeroNode getHead() {
        return head;
    }

    public void setHead(HeroNode head) {
        this.head = head;
    }

    /**
     * 添加元素 不考虑编号顺序的情况
     */
    public void add(HeroNode node) {
        // 1.找到链表最后节点
        // 2.将最后节点的next指向新节点

        //需要一个辅助指针 因为头节点不能改动
        HeroNode temp = head;
        while (true) {
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
        temp.next = node;
    }

    /**
     * 添加元素 考虑编号顺序的情况 增长排序，节点序号递增
     */
    public void addByOrder(HeroNode node) {
        // 1.找到新添加节点在链表中应该存在的位置(用temp)
        // 2.temp指针指向该位置的前一个节点
        // 3.temp的next交给node的next
        // 4.将temp的next重新指向node
        HeroNode temp = head;
        boolean isExist = false;
        while (true) {
            //考虑若next为空的情况 此时已遍历到链表最后
            //插入动作是一样的 将temp.next即null交给node.next，再将temp.next重新指向node
            if (temp.next == null) {
                break;
            }
            if(temp.next.no > node.no) {//找到第一个比插入序号大的节点，就找到了正确位置：temp指向的节点
                //插入temp的后面
                break;
            } else if (temp.next.no == node.no) {
                //编号已存在
                isExist = true;
                break;
            }
            temp = temp.next;
        }
        if (isExist) {
            System.out.println("编号信息已存在");
        }
        node.next = temp.next;
        temp.next = node;
    }

    public void list() {
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("空链表");
            return;
        }
        HeroNode temp = head.next;
        while (true) {
            if (temp == null) {
                break;
            }
            //输出节点信息
            System.out.println(temp.toString());
            //后移 注意否则是死循环
            temp = temp.next;
        }
    }

    //删除
    //1.找到待删除节点的前一个节点
    //2.将前一个节点的next指针指向待删除节点的下一个节点即可，这就完成了删除
    //3.被删除的节点（对象），由于没有任何引用指向，因此会被垃圾回收
    public void del(int no) {
        HeroNode temp = head;
        boolean flag = false;
        while (true) {
            if (temp.next == null) {
                flag = true;
                break;
            }
            if (temp.next.no == no) {
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            System.out.println("链表无节点匹配");
        } else {
            temp.next = temp.next.next;//删除
        }
    }

    /**
     * 有效节点的个数
     * @param head
     * @return
     */
    public static int size(HeroNode head) {
        int size = 0;
        HeroNode temp = head;
        while (true) {
            if (temp.next == null) {
                break;
            }
            size++;
            temp = temp.next;
        }
        return size;
    }

    /**
     * 查找单链表中倒数第k个节点
     */
    public HeroNode findLastIndexNode(HeroNode head ,int k) {
        //1.求得size
        //2.遍历（size - k）次得到
        if (head.next == null) {
            return null;
        }
        int size = size(head);
        //先做index校验
        if (k < 0 || k > size) {
            return null;
        }
        HeroNode cur = head.next;//第一个
        for (int i = 0; i < size - k; i++) {
            cur = head.next;//每次往后移动一下
        }
        return cur;
    }

    /**
     * 链表反转
     */
    public void reverse(HeroNode node) {
        //1.先定义一个新节点
        //2.从头到尾遍历原来的链表，每次将节点放在新链表的最前端（关键一步）
        //3.将旧链表的头节点的next指针指向新链表
        if (head.next == null || head.next.next == null) {
            return;
        }
        HeroNode cur = head.next;//指针，指向遍历的当前节点
        HeroNode next = null;//指向cur的下一节点
        HeroNode reverseHead = new HeroNode(0, "", "");
        while (cur != null) {
            next = cur.next;//保留当前节点的下一节点的指针
            //关键一步 摘下cur放到新链表第一个节点：插到新链表的第一个节点之前，那么它的next指针应指向新链表的第一个节点。
            cur.next = reverseHead.next;
            //此时旧链表当前节点可看作已被摘下（）
            reverseHead.next = cur;//将新链表头节点指向该节点
            cur = next;//cur后移
        }
        head.next = reverseHead.next;//赋值给旧链表
    }

    /**
     * 从尾部到头打印单链表
     */
    public void printListFromLast(HeroNode head) {
        //方法1 先反转后打印 浪费空间 破坏了原有数据 不推荐
        //方法2 栈
        if (head.next == null) {
            return;
        }
        Stack<HeroNode> stack = new Stack<HeroNode>();
        //将链表的所有元素压入栈中
        HeroNode cur = head.next;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        //将栈进行打印
        while (stack.size() > 0) {
            System.out.println(stack.pop());
        }
    }

    /**
     * 合并两个有序链表 合并后仍然有序
     */
    public static HeroNode combineSortedList(HeroNode head1, HeroNode head2) {
        //1.定义新链表
        //2.addByOrder有序加入即可
        HeroNode combineHead = new HeroNode(0, "", "");

        HeroNode cur1 = head1.next;
        HeroNode cur2 = head2.next;

        while (cur1 != null) {
            HeroNode temp = combineHead;//定义指针遍历合并链表combineHead
            boolean flag = false;
            while (true) {
                if (temp.next == null) {
                    break;
                }
                if (temp.next.no > cur1.no) {
                    break;
                } else if (temp.next.no == cur1.no) {
                    flag = true;
                    break;
                }
                temp = temp.next;
            }
            if (flag) {
                //重复数据
            }
            //插入
            HeroNode next = cur1.next;//先存下来

            cur1.next = temp.next;
            temp.next = cur1;

            cur1 = next;//后移
        }

        while (cur2 != null) {
            HeroNode temp = combineHead;//定义指针遍历合并链表combineHead
            boolean flag = false;
            while (true) {
                if (temp.next == null) {
                    break;
                }
                if (temp.next.no > cur2.no) {
                    break;
                } else if (temp.next.no == cur2.no) {
                    flag = true;
                    break;
                }
                temp = temp.next;
            }
            if (flag) {
                //重复数据
            }
            //插入
            HeroNode next = cur2.next;//先存下来
            cur2.next = temp.next;
            temp.next = cur2;

            cur2 = next;
        }

        return combineHead;
    }


}

//定义节点
class HeroNode {
    public int no;
    public String name;
    public String nickName;
    public HeroNode next;

    public HeroNode(int no, String name, String nickName) {
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                '}';
    }
}
